package com.leetcode;

import com.leetcode.common.TreeNode;
import com.leetcode.util.BinaryTreeUtil;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 297. 二叉树的序列化与反序列化
 * https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
 * 深度优先搜索
 * 遍历
 *
 * @author fy
 * @date 2022/4/12 19:30
 */
public class Solution297 {

//    private final static String NULL_STR = "None";
    private final static String NULL_STR = "null";

    public String serialize(TreeNode root) {
        return rserialize(root, "");
    }

    public TreeNode deserialize(String data) {
        String[] dataArray = data.split(",");
        List<String> dataList = new LinkedList<String>(Arrays.asList(dataArray));
        return rdeserialize(dataList);
    }

    private String rserialize(TreeNode root, String str) {
        if (root == null) {
            str += NULL_STR + ",";
        } else {
            str += root.val + ",";
            str = rserialize(root.left, str);
            str = rserialize(root.right, str);
        }
        return str;
    }

    private TreeNode rdeserialize(List<String> dataList) {
        if (dataList.get(0).equals(NULL_STR)) {
            dataList.remove(0);
            return null;
        }

        TreeNode root = new TreeNode(Integer.parseInt(dataList.get(0)));
        dataList.remove(0);
        root.left = rdeserialize(dataList);
        root.right = rdeserialize(dataList);

        return root;
    }

    public static void main(String[] args) {
        Integer[] nums = new Integer[]{1, 2, 3, null, null, 4, 5};
        TreeNode root = BinaryTreeUtil.createTree(nums);
        BinaryTreeUtil.printTree(root);

        String res = new Solution297().serialize(root);
        System.out.println(res);

        TreeNode newRoot = new Solution297().deserialize(res);
        BinaryTreeUtil.printTree(newRoot);
    }

}
